존슨 알고리즘(Johnson Algorithm)

모든 쌍의 최단 경로를 O(V^2 lgV+VE)시간에 찾는다.

희소 그래프에서 대해서 플로디으 워샬 알고리즘이나, 행렬을 반복적으로 곱하는 연산보다 빠르다.

존슨 알고리즘의 리턴값은 최소 경로 가중치의 행렬이거나 음의 가중치를 가지는 순환값의 유무에 대한 정보를 포함

존슨 알고리즘은 서브 루틴으로 Bellman-Ford & Dijkstra Algorithm을 사용

존슨 알고리즘의 과정 초반에 s(시작점)을 생성하고 연산을 수행함

가중치 조정(Reweighting) 새로운 가중치 함수 ŵ (u,v) $\hat{w}(u, v)$ 를 정의해서 사용한다 가중치 함수를 얻은 최단 경로 가중치: δ̂ $\hat{\delta}$ ŵ (u,v)=w(u,v)+h(u)−h(v) $\hat{w}(u, v)=w(u, v)+h(u)-h(v)$ h(v)=δ(s,v) $h(v)=\delta(s, v)$ w:E→ℝ $w: E\rightarrow \mathbb{R}$ h:V→ℝ $h: V\rightarrow \mathbb{R}$

Reweighting은 최단 경로의 보존하며, 음이 아닌 가중치로 만들어 준다.

introduction to Algorithms 3rd Edition(한글본; Korean Trasistion) pg.721